package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

import java.util.Arrays;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/combination-sum-iv/">k</a>
 */
public class Solution377 extends BaseSolution {

    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] rst = new int[target + 1];
        rst[0] = 1;
        for (int sum = 1; sum <= target; sum++) {
            for (int i = 0; i < nums.length && nums[i] <= sum; i++) {
                rst[sum] += rst[sum - nums[i]];
            }
        }
        return rst[target];
    }

    public static void main(String[] args) {
        Solution377 solution = new Solution377();
        System.out.println(solution.combinationSum4(new int[] {
                1,2,3
        }, 4));
    }
}